/*
 * One example for NOI CSP-J Lesson 9:
 * <https://courses.fmsoft.cn/plzs/noijunior-csp-exercises-lower.html>
 *
 * Author: Vincent Wei
 *  - <https://github.com/VincentWei>
 *  - <https://gitee.com/vincentwei7>
 *
 * Copyright (C) 2025 FMSoft <https://www.fmsoft.cn>.
 * License: GPLv3
 */
#include <vector>
#include <iostream>
#include <cassert>

using namespace std;

vector<unsigned> counting_sort(const vector<unsigned> &a, unsigned maxv)
{
    unsigned n = a.size();
    vector<unsigned> cnt(maxv + 1, 0);

    // 计算各值出现的次数。
    for (unsigned i = 0; i < n; i++)
        cnt[a[i]]++;

    // 计算各值出现次数的前缀和。前缀和记录的是每个值在排序之后的位置。
    for (unsigned i = 1; i <= maxv; i++) {
        cnt[i] += cnt[i - 1];
    }

    // 利用出现次数的前缀和，从右至左完成每个数的排名。
    vector<unsigned> sorted(n, 0);
    for (unsigned i = n; i >= 1; i--) {
        sorted[--cnt[a[i - 1]]] = a[i - 1];
    }

    return sorted;
}


int main() {
    vector<unsigned> a = { 2, 2, 5, 1, 3, 1, 4, 1, 5 };
    vector<unsigned> expected = {1, 1, 1, 2, 2, 3, 4, 5, 5};
    vector<unsigned> sorted = counting_sort(a, 10);

    assert(sorted == expected);
    return 0;
}
